class Solution {
public:
    int uniquePaths(int m, int n) {
        //dp[i][j]代表机器人从00位置开始到达ij位置存在多少条不同的路径
        // 因为机器人只能往下或者往右移动，所以机器人要到达ij位置只能从i-1,j位置到达，或者从i,j-1位置到达
        // 由此就能够得到状态转移方程了:
        // dp[i][j] = dp[i-1][j] + dp[i][j-1]
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        dp[1][1] = 1;//从11位置开始到达11位置的路线就是一条
        for(int i = 1;i<=m;i++)
        {
            for(int j = 1;j<=n;j++)
            {
                if(i == 1&&j == 1)
                {
                    continue;
                }
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};
class Solution {
public:
    vector<vector<int>> mem;
    int dfs(int m,int n)
    {
        if(mem[m][n]!=0)
        {
            return mem[m][n];//查询记忆化数组看是否dfs过
        }
        if(m == 1&&n == 1)
        {
            mem[m][n] = 1;
            return 1;
        }
        if(m == 0||n == 0)
        {
            return 0;
        }
        mem[m][n] = dfs(m-1,n)+dfs(m,n-1);
        return mem[m][n];
    }
    int uniquePaths(int m, int n) {
        mem.resize(m+1,vector<int>(n+1,0));
        return dfs(m,n);
    }
};//使用dfs+记忆化数组来解决